等价于求字符串的最长公共前缀。
1
2
3
4
5
6
7
8
9
10
| class Solution {
public int findMinimumOperations(String s1, String s2, String s3) {
int n = Math.min(s1.length(), Math.min(s2.length(), s3.length()));
int i = 0;
while (i < n && s1.charAt(i) == s2.charAt(i) && s2.charAt(i) == s3.charAt(i)) {
i++;
}
return i == 0 ? -1 : s1.length() + s2.length() + s3.length() - 3 * i;
}
}
|
将每个 \(1\) 右边 \(0\) 的个数累加就是需要交换的次数，或者累加每个 \(0\) 左边 \(1\) 的个数也行。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public long minimumSteps(String s) {
long ans = 0L;
int n = s.length(), cnt = 0;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == '0') cnt++;
else ans += cnt;
}
return ans;
}
}
|
要求 \(\max((a\oplus x)\times(b\oplus x))\)，可以得出异或只会在两者都为 \(0\) 的位上补 \(1\)，或者交换两者某位上的 \(0\) 和 \(1\)。此时 \((a\oplus x)+(b\oplus x)=c\)，\(c\) 为某个定值，从而问题可以转化为求函数 \(y=x(c-x)\) 的最大值，可以知道当 \(x=\frac{c}{2}\) 时取到最大值，即我们需要让 \((a\oplus x)\) 和 \((b\oplus x)\) 尽可能相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int maximumXorProduct(long a, long b, int n) {
long p = a >> n << n, q = b >> n << n;
for (int i = n - 1; i >= 0; i--) {
if ((a >> i & 1) == (b >> i & 1)) {
p |= 1L << i;
q |= 1L << i;
} else if (p < q) {
p |= 1L << i;
} else {
q |= 1L << i;
}
}
return (int) (p % MOD * (q % MOD) % MOD);
}
}
|
离线查询，可以预处理查询序列，然后使用单调栈 + 二分，或者使用最小堆；在线查询，可以使用线段树（暂时不学）。